// 双向队列存下标
fn rs_main1(nums: Vec<i32>, k: i32) -> Vec<i32> {
  use std::collections::VecDeque;

  let len = nums.len();
  if len <= 1 || k == 1 {
    return nums;
  }
  let mut result: Vec<i32> = Vec::new();
  let mut queue: VecDeque<usize> = VecDeque::new();
  let width = k as usize - 1;

  for right in 0..len {
    while !queue.is_empty() && *nums.get(right).unwrap() >= nums[*queue.back().unwrap()] {
      queue.pop_back();
    }
    queue.push_back(right);
    if right >= width {
      let left = right - width;
      if *queue.front().unwrap() < left {
        queue.pop_front();
      }
      result.push(nums[*queue.front().unwrap()]);
    }
  }
  return result;
}

// 双向队列存值
fn rs_main2(nums: Vec<i32>, k: i32) -> Vec<i32> {
  use std::collections::VecDeque;

  let len = nums.len();
  if len <= 1 || k == 1 {
    return nums;
  }
  let mut result: Vec<i32> = Vec::new();
  let mut queue: VecDeque<i32> = VecDeque::new();
  let width = k - 1;

  for right in 0..len {
    while !queue.is_empty() && *queue.back().unwrap() < *nums.get(right).unwrap() {
      // 该循环能保证队列前面元素的下标一定在其后元素的左侧
      queue.pop_back();
    }
    queue.push_back(*nums.get(right).unwrap());
    if right >= width as usize { // 滑动窗口
      result.push(*queue.front().unwrap()); // 将最大值push到结果数组
      // 判断窗口最后一位元素是否最大值，如果是则移除，保证下一次窗口移动时不会有跃出边界的值
      if *queue.front().unwrap() == *nums.get(right - width as usize).unwrap() {
        queue.pop_front();
      }
    }
  }
  return result;
}


fn main() {
  println!("{:?}", rs_main1(vec![1, 3, -1, -3, 5, 3, 6, 7], 3));
  println!("{:?}", rs_main1(vec![1], 1));
  println!("{:?}", rs_main1(vec![1, -1], 1));
  println!("{:?}", rs_main1(vec![9, 11], 2));
  println!("{:?}", rs_main1(vec![4, -2], 2));
  println!("{:?}", rs_main2(vec![1, 3, -1, -3, 5, 3, 6, 7], 3));
  println!("{:?}", rs_main2(vec![1], 1));
  println!("{:?}", rs_main2(vec![1, -1], 1));
  println!("{:?}", rs_main2(vec![9, 11], 2));
  println!("{:?}", rs_main2(vec![4, -2], 2));
}
